package com.cat.binaryTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/balance-a-binary-search-tree/description/
 * @create 2025/9/28 17:53
 * @since JDK17
 */

public class Solution79 {
    List<Integer> list = new ArrayList<>();

    void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
    TreeNode f(List<Integer> list, int l, int r) {
        if (l > r) {
            return null;
        }
        int m = l + r >> 1;
        return new TreeNode(list.get(m), f(list, l, m - 1), f(list, m + 1, r));
    }

    public TreeNode balanceBST(TreeNode root) {
        dfs(root);
        return f(list, 0, list.size() - 1);
    }
}
